Search results for "regular operation"

showing 2 items of 2 documents

Complexity of operations on cofinite languages

2010

International audience; We study the worst case complexity of regular operation on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.

Nested wordTheoretical computer scienceSettore INF/01 - Informaticaautomata[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]regular operationReDoSComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technologyDescriptive complexity theorystate complexity01 natural sciencesComplement (complexity)Deterministic finite automaton010201 computation theory & mathematicsTheory of computation0202 electrical engineering electronic engineering information engineeringComputer Science::Programming LanguagesQuantum finite automata020201 artificial intelligence & image processingNondeterministic finite automatoncofinite languageMathematics
researchProduct

The average state complexity of rational operations on finite languages is linear

2010

Considering the uniform distribution on sets of m non-empty words whose sum of lengths is n, we establish that the average state complexities of the rational operations are asymptotically linear.

finite languages regular operations automata state complexity average case analysisSettore INF/01 - Informatica
researchProduct